package com.dragon.datastructure.linkedlist;

import java.util.Random;

/**
 * 合并两个有序的单链表，合并之后的链表依然有序
 *
 * @author dragon
 * @since 2019/12/17
 */
public class Test5 {

    private static class Node {
        Node next;
        int item;
    }

    public static Node mergeTwoListIter(Node n1, Node n2) {
        Node dummyNode = new Node();
        Node prev = dummyNode;
        while (n1 != null && n2 != null) {
            if (n1.item < n2.item) {
                prev.next = n1;
                n1 = n1.next;
                prev = n1;
            } else {
                prev.next = n2;
                n2 = n2.next;
                prev = n2;
            }
        }
        prev.next = n1 == null ? n2 : n1;

        return dummyNode.next;
    }

    public static Node mergeTwoListRecursion(Node n1, Node n2) {
        if (n1 == null) {
            return n2;
        }
        if (n2 == null) {
            return n1;
        }

        if (n1.item < n2.item) {
            n1.next = mergeTwoListRecursion(n1.next, n2);
            return n1;
        } else {
            n2.next = mergeTwoListRecursion(n1, n2.next);
            return n2;
        }
    }
}
